// newton_interpolation.hpp
#ifndef NEWTON_INTERPOLATION_HPP
#define NEWTON_INTERPOLATION_HPP

#include <vector>
#include <functional>
#include <stdexcept>

class NewtonInterpolation {
public:
      // 默认构造函数
    NewtonInterpolation() = default;
    // 使用已知的数据点构造插值多项式
    NewtonInterpolation(const std::vector<double>& x, const std::vector<double>& y) {
        if (x.size() != y.size()) {
            throw std::invalid_argument("The size of x and y must be equal.");
        }
        int n = x.size();
        coef_.resize(n);
        x_.resize(n);
        coef_.assign(y.begin(), y.end());
        x_.assign(x.begin(), x.end());

        for (int level = 1; level < n; ++level) {
            for (int i = n - 1; i >= level; --i) {
                coef_[i] = (coef_[i] - coef_[i - 1]) / (x_[i] - x_[i - level]);
            }
        }
    }

    // 使用构造的插值多项式计算给定点的插值结果
    double interpolate(double z) const {
        int n = coef_.size();
        double result = coef_[n - 1];
        for (int i = n - 2; i >= 0; --i) {
            result = result * (z - x_[i]) + coef_[i];
        }
        return result;
    }

private:
    std::vector<double> coef_; // 存储插值多项式的系数
    std::vector<double> x_;    // 存储原始的x值，用于插值时计算
};

#endif
